package A一周刷爆LeetCode.A基础班.F二叉树;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * @author wei.zhao
 * @description: 判断一颗二叉树是否是满二叉树
 * @date 2022年02月24日 11:17
 */
public class Code08_IsFBT {

    public static void main(String[] args) {
        Node head = new Node(7);
        head.left = new Node(5);
        head.right = new Node(9);
        head.left.left = new Node(4);
        head.left.right = new Node(6);
        head.right.left = new Node(8);
        head.right.right = new Node(10);
        System.out.println("是否是满二叉树：" + isFBT01(head));
        System.out.println("是否是满二叉树：" + isFBT02(head));
    }

    private static Boolean isFBT01(Node head) {
        LinkedList<Node> list = new LinkedList<>();
        list.add(head);
        HashMap<Node, Integer> map = new HashMap<>();
        map.put(head, 1);
        int maxLevel = 1;
        int count = 0;
        while (!list.isEmpty()) {
            Node node = list.pop();
            count++;
            if (node.left != null) {
                list.add(node.left);
                maxLevel = map.get(node) + 1;
                map.put(node.left, maxLevel);
            }
            if (node.right != null) {
                list.add(node.right);
                maxLevel = map.get(node) + 1;
                map.put(node.right, maxLevel);
            }
        }
        return count == Math.pow(2, maxLevel) - 1;
    }

    private static Boolean isFBT02(Node head) {
        Result result = getResult(head);
        return result.count == Math.pow(2, result.level) - 1;
    }

    private static Result getResult(Node node) {
        if (null == node) {
            return new Result(0, 0);
        }
        Result left = getResult(node.left);
        Result right = getResult(node.right);
        return new Result(Math.max(left.level, right.level) + 1, left.count + right.count + 1);
    }

    public static class Result {
        public Integer level;
        public Integer count;

        public Result(Integer level, Integer count) {
            this.level = level;
            this.count = count;
        }
    }

}
